package src;

import java.util.*;

public class Algorithm {

	public Algorithm(String graphFileName) {
		SimpleGraph graph = new SimpleGraph();
		Hashtable table;
		table = GraphInput.LoadSimpleGraph(graph, graphFileName);
		List<Edge> edges = primAlgorithm(graph);
		
		double total = 0;
		for (Edge e : edges) {
			if (e != null) {
				total += (double) e.getData();
				System.out.println("\tEdge " + e.getName() + ", going from " 
							   + e.getFirstEndpoint().getName() + "to " 
							   + e.getSecondEndpoint().getName());
			}
		}
		System.out.println("The total weight of the edges is: " + total);
	}
	
	public List<Edge> primAlgorithm(SimpleGraph graph) {
		List<Edge> usedEdges = new ArrayList<Edge>();
		
		BinaryHeap primHeap = new BinaryHeap(graph.numVertices());
		Vertex initialV = graph.aVertex();
		PrimHeapNode currentNode = null;
		for (int i = 0; i < graph.vertexList.size(); i++) {
			Vertex v = (Vertex)graph.vertexList.get(i);
			v.setData(new PrimHeapNode(v));
		}

		primHeap.insert((Comparable) initialV.getData());
//		try {
//			primHeap.deleteMin();
//		} catch (EmptyHeapException e1) {
//			// TODO Auto-generated catch block
//			e1.printStackTrace();
//		}
		
		while(!primHeap.isEmpty()) {
			try {
				currentNode = (PrimHeapNode) primHeap.deleteMin();
				currentNode.setUsed();
				usedEdges.add(currentNode.getLeastEdge()); 
				ArrayList<Vertex> adjacentVertices = currentNode.getAdjacentVertices();
				if (adjacentVertices != null) {
					for (int y = 0; y < adjacentVertices.size(); y++){// Vertex v : adjacentVertices) {
						if (!((PrimHeapNode) adjacentVertices.get(y).getData()).isUsed() )
//								&& !usedEdges.contains(adjacentVertices.get(y).incidentEdgeList.get(y)))
							primHeap.insert((Comparable) adjacentVertices.get(y).getData());
							currentNode.setUsed();
					}
				}	

			} catch(EmptyHeapException e) {
				e.printStackTrace();
			}
			
		}
		
		
		return usedEdges;
	}
}
